package topcoder.srm572;

import java.util.Arrays;

public class NextOrPrev {

	public int getMinimum(int nc, int pc, String start, String goal) {
		int[] E = new int[start.length()];
		char[] sc = start.toCharArray();
		char[] gc = goal.toCharArray();

		E[0] = Math.min(prevCost(sc, gc, 0, pc), nextCost(sc, gc, 0, nc));

		for (int i = 1; i < start.length(); i++) {
			System.out.println("i = " + i + ", " + nextCost(sc, gc, i, nc)
					+ E[i - 1]);

			E[i] = Math.min(prevCost(sc, gc, i, pc) + E[i - 1],
					nextCost(sc, gc, i, nc) + E[i - 1]);
		}

		System.out.println(Arrays.toString(E));
		return E[start.length() - 1];
	}

	private int nextCost(char[] sc, char[] gc, int i, int nc) {
		if (sc[i] == gc[i])
			return 0;
		if (sc[i] > gc[i]) {
			System.out.println("i = " + i);
			return 10000000;
		}
		System.out.printf("sc=%c, gc=%c, nextCost=%d\n", sc[i], gc[i],
				(gc[i] - sc[i]) * nc);
		return ((int) (gc[i] - sc[i])) * nc;
	}

	private int prevCost(char[] sc, char[] gc, int i, int pc) {
		if (sc[i] == gc[i])
			return 0;
		if (sc[i] < gc[i])
			return 10000000;
		System.out.printf("sc=%c, gc=%c, prevCost=%d\n", sc[i], gc[i],
				(sc[i] - gc[i]) * pc);
		return (sc[i] - gc[i]) * pc;

	}

	public static void main(String[] args) {
		NextOrPrev np = new NextOrPrev();
		System.out.println(np.getMinimum(1000, 1000, "abcdefghijklz", "mnopqrstuvwxy"));
	}
}
